/*
 * 8puzzle.cpp
 *
 *  Created on: 7-May-09
 *      Author: marduke
 */

#include "8puzzle.h"


int main(int argc, char **argv) {
	char* algoritmo;
	char* accion;
	state *estado;
	int i;
	coordenada pos;
	unsigned long valor;

	if (argc != 11) {
		printf("Faltan argumentos para la execucion del programa\n");
		exit(0);
	}

	estado = (state *) malloc (sizeof (state));
	algoritmo = (char *) malloc(sizeof(char)*3);
	strcpy(algoritmo, argv[1]);
	estado->valor = atoi(argv[2]) * 100000000 +  atoi(argv[3]) * 10000000 +  atoi(argv[4]) * 1000000 + atoi(argv[5]) * 100000 +  atoi(argv[6]) * 10000 + atoi(argv[7]) * 1000 +  atoi(argv[8]) * 100 +  atoi(argv[9]) * 10 +  atoi(argv[10]);
	estado->padre = NULL;

	printf("El estado es: %ld \n", estado->valor);



	pos = getCero(estado->valor);
	cout << "La Coordenada es: (" << pos.x << "," << pos.y << ")" << endl;

	list<state *> estados;
	list<state *>::iterator it;
	estados = estadosSiguientes(estado);//

	bfs(estado);

}

coordenada getCero(unsigned long estadoActual) {

	int i;
	int j;
	coordenada pos;
	long estado = estadoActual;

	for (i = 2; i >= 0; i--) {
		for (j = 2; j >= 0; j--) {
			if (estado == 0) {
				pos.x = i;
				pos.y = j;
				return pos;
			}

			if (estado % 10 == 0) {
				pos.x = i;
				pos.y = j;
				return pos;
			} else {
				estado = estado / 10;
			}
		}
	}

}

list<state *> estadosSiguientes(state *estadoActual) {

	coordenada pos = getCero(estadoActual->valor);
	coordenada tmp;
	tmp.x=pos.x;
	tmp.y=pos.y;

	list<state *> estados;

	if (pos.x + 1 < 3) {
		tmp.x++;
		estados.push_back(hacerMovimiento(estadoActual, posicionLong(pos),posicionLong(tmp)));
		tmp.x--;
		}
	if (pos.x - 1 >= 0){
		tmp.x--;
		estados.push_back(hacerMovimiento(estadoActual, posicionLong(pos),posicionLong(tmp)));
		tmp.x++;
		}
	if (pos.y + 1 < 3) {
		tmp.y++;
		estados.push_back(hacerMovimiento(estadoActual, posicionLong(pos),posicionLong(tmp)));
		tmp.y--;
	}
	if (pos.y - 1 >= 0){
		tmp.y--;
		estados.push_back(hacerMovimiento(estadoActual, posicionLong(pos),posicionLong(tmp)));
		tmp.y++;
		}

	return estados;
}

state *hacerMovimiento(state *estado,int pos0, int posM) {
	unsigned long nM;
	unsigned long nE;
	state *retorno;

	retorno = (state *) malloc (sizeof(state));

	retorno->padre= estado;

	nM =  estado->valor / ((unsigned long) pow(10, posM-1));
	nM = nM % 10;

	nE = estado->valor - (nM * ((unsigned long) pow(10, posM-1)));
	retorno->valor = nE + (nM * ((unsigned long) pow(10, pos0-1)));


    return retorno;

}

int posicionLong(coordenada pos) {
	return (2 - pos.x)*3 + (3-pos.y);
}

unsigned long bfs(state *estado) {

	list<state*> queue;
	list<state*> acciones;
	list<unsigned long> cerrados;
	list<state*>::iterator it;
	state *actual;
	state *tmp;
	queue.push_back(estado);
	cerrados.push_back(estado->valor);


	do {
	actual = queue.front();
	queue.pop_front();
	acciones = estadosSiguientes(actual);



	it = acciones.begin();

	while (it != acciones.end()) {
		/*Aqui deberia ir un if que verifica si los estados expandidos no sean la solucion y si existe*/

		tmp = *it;
		if (estaVisitado(cerrados,tmp->valor)) {
//		cout << "El valor es: " << tmp->valor << " Y el padre es: " << tmp->padre->valor << endl;
		queue.push_back(tmp);
		} else {
			free(tmp);

		}
		*it++;


	}

	} while (actual->valor != 12345678);

	cout << "Dato importante " << actual->valor << endl;
	conseguirCamino(actual);
	cout << "SALI" << endl;
}



void conseguirCamino (state *final) {

	state *actual = final;
	list<char *> camino;
	int n=0;
	while (actual->padre != NULL) {
		n++;
		cout << "Y go " << actual->valor << " el padre es: "<<actual->padre->valor << "El movimiento fue: " << conseguirMov(actual->valor,actual->padre->valor) << endl;
		actual = actual->padre;

	}

}

char *conseguirMov(unsigned long est1, unsigned long est2) {
	coordenada pos1 = getCero(est1);
	coordenada pos2 = getCero(est2);

	if(pos1.x -pos2.x == 1)
			return "DOWN";
	if (pos1.x -pos2.x == -1)
			return "UP";
	if (pos1.y - pos2.y == 1)
			return "RIGTH";
	if (pos1.y - pos2.y == -1)
			return "LEFT";
}

bool estaVisitado(list<unsigned long> estado, unsigned long actual) {

	list<unsigned long>::iterator it;
	it = estado.begin();

	while (it != estado.end()) {

		if ( *it++ == actual) {
			return false;
		}
	}
	return true;
}
